# import random
#
# import matplotlib.pyplot as plt
# from matplotlib.animation import FuncAnimation
# from matplotlib.patches import Circle
# import heapq
# from collections import defaultdict
#
#
# class Node:
#     def __init__(self, freq, symbol='', left=None, right=None):
#         self.freq = freq
#         self.symbol = symbol
#         self.left = left
#         self.right = right
#
#     def __lt__(self, other):
#         return self.freq < other.freq
#
#
# def huffman_tree_visual(ax):
#     data = [random.randint(1, 10) for _ in range(10)]
#     freq_dict = defaultdict(int)
#
#     for item in data:
#         freq_dict[item] += 1
#
#     def build_huffman_tree():
#         heap = [Node(freq, symbol) for symbol, freq in freq_dict.items()]
#         heapq.heapify(heap)
#         trees = []
#
#         while len(heap) > 1:
#             node1 = heapq.heappop(heap)
#             node2 = heapq.heappop(heap)
#             merged = Node(node1.freq + node2.freq, left=node1, right=node2)
#             heapq.heappush(heap, merged)
#             trees.append(merged)
#
#         trees.append(heap[0])
#         return trees
#
#     def draw(tree, ax, x=0, y=0, depth=0, color='blue'):
#         if tree is None:
#             return
#
#         circle = Circle((x, y), 8, color=color, fill=True, edgecolor='black')
#         ax.add_patch(circle)
#
#         ax.text(x, y, f'{tree.symbol}:{tree.freq}' if tree.symbol else f'[{tree.freq}]', fontsize=12, ha='center',
#                 va='center', color='white')
#
#         spacing = 20 * depth
#
#         if tree.left:
#             draw(tree.left, ax, x - (50 - spacing), y - 40, depth + 1, 'blue')
#             ax.plot([x, x - (50 - spacing)], [y, y - 40], 'k-')
#             ax.text(x - (50 - spacing) / 2, (2 * y - 40) / 2, '0', fontsize=12, ha='center', va='top', color='black')
#
#         if tree.right:
#             draw(tree.right, ax, x + (50 - spacing), y - 40, depth + 1, 'green')
#             ax.plot([x, x + (50 - spacing)], [y, y - 40], 'k-')
#             ax.text(x + (50 - spacing) / 2, (2 * y - 40) / 2, '1', fontsize=12, ha='center', va='top', color='black')
#
#     def update(frame, ax, trees):
#         ax.clear()
#         draw(trees[frame], ax)
#         ax.set_xlim(-100, 100)
#         ax.set_ylim(-150, 50)
#         ax.axis('off')
#
#     trees = build_huffman_tree()
#     ani = FuncAnimation(ax.figure, update, frames=range(len(trees)), fargs=(ax, trees), interval=1000, repeat=False)
#     return ani


import random
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from matplotlib.patches import Circle
import heapq
from collections import defaultdict

class Node:
    def __init__(self, freq, symbol='', left=None, right=None):
        self.freq = freq
        self.symbol = symbol
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq


data = None

def huffman_tree_visual(ax):
    # data = [random.randint(1, 10) for _ in range(10)]
    data = [5, 29, 3, 8, 5, 23, 3, 11]
    freq_dict = defaultdict(int)

    for item in data:
        freq_dict[item] += 1

    data_str = ', '.join(f'{symbol}:{freq}' for symbol, freq in freq_dict.items())

    def build_huffman_tree():
        heap = [Node(freq, symbol) for symbol, freq in freq_dict.items()]
        heapq.heapify(heap)
        trees = []

        while len(heap) > 1:
            node1 = heapq.heappop(heap)
            node2 = heapq.heappop(heap)
            merged = Node(node1.freq + node2.freq, left=node1, right=node2)
            heapq.heappush(heap, merged)
            trees.append(merged)

        trees.append(heap[0])
        return trees

    def draw(tree, ax, x=0, y=0, depth=0, color='blue'):
        if tree is None:
            return

        circle = Circle((x, y), 8, color=color, fill=True, edgecolor='black')
        ax.add_patch(circle)

        ax.text(x, y, f'{tree.symbol}:{tree.freq}' if tree.symbol else f'[{tree.freq}]', fontsize=12, ha='center',
                va='center', color='white')

        spacing = 20 * depth

        if tree.left:
            draw(tree.left, ax, x - (50 - spacing), y - 40, depth + 1, 'blue')
            ax.plot([x, x - (50 - spacing)], [y, y - 40], 'k-')
            ax.text(x - (50 - spacing) / 2, (2 * y - 40) / 2, '0', fontsize=12, ha='center', va='top', color='black')

        if tree.right:
            draw(tree.right, ax, x + (50 - spacing), y - 40, depth + 1, 'green')
            ax.plot([x, x + (50 - spacing)], [y, y - 40], 'k-')
            ax.text(x + (50 - spacing) / 2, (2 * y - 40) / 2, '1', fontsize=12, ha='center', va='top', color='black')

    def update(frame, ax, trees):
        ax.clear()
        draw(trees[frame], ax)
        ax.set_xlim(-100, 100)
        ax.set_ylim(-150, 50)
        # ax.axis('off')
        # ax.text(0, 40, f'Data: [{data_str}]', fontsize=12, ha='center')
        ax.text(0, 40, f'Data: {data}', fontsize=12, ha='center')

    trees = build_huffman_tree()
    ani = FuncAnimation(ax.figure, update, frames=range(len(trees)), fargs=(ax, trees), interval=1000, repeat=False)
    return ani

